1. Field of the Invention
The present invention relates to an error correcting decoding apparatus for an extended Reed-Solomon code for decoding extended Reed-Solomon codes (abbreviated to extended RS codes from now on) which are used as a code capable of correcting errors occurring in digital radio communications and digital magnetic recording, and to an error correcting apparatus for a singly or doubly extended RS code for correcting errors occurring in the digital radio communications and digital recording.
2. Description of Related Art
First, the structure of a singly extended RS code will be described which is subjected to error correcting decoding in the present invention. For the purpose of simplicity, we assume that the characteristic of the Galois field is two.
A singly extended RS code with a code length of n and an information symbol number of k can be formed as follows. First, an information polynomial with the following expression (1) is formed for information symbols (c.sub.n-2, c.sub.n-3, . . . , c.sub.n-k-1) consisting of the elements of the Galois field. EQU c.sub.n-2 x.sup.n-2 +c.sub.n-3 .sup.n-3 + . . . +c.sub.n-k-1 x.sup.n-k-1 ( 1)
Then, the information polynomial is divided by a generator polynomial given by the following expression (2). EQU g(x)=(x-.alpha..sup.b)(x-.alpha..sup.b+1) . . . (x-.alpha..sup.b+n-k-2) (2)
where b is a predetermined integer, and a is a root of a primitive polynomial forming the Galois field.
Thus, when the remainder polynomial obtained by the division by the foregoing expression (2) is given by the following expression (3), (c.sub.n-2, C.sub.n-3, . . . , c.sub.1, c.sub.0) is generated by adding coefficient information of (n-k-1) symbols as check symbols. EQU c.sub.n-k-2 x.sup.n-k-2 +c.sub.n-k-3 x.sup.n-k-3 + . . . +c.sub.1 x+c.sub.0 (3)
Furthermore, a code word c=(c.sub.n-2, c.sub.n-3, . . . , c.sub.1, c.sub.0, c.sub.-1) of a singly extended RS code is formed by adding as a final symbol a value c.sub.-1 generated by the following equation (4). EQU c.sub.-1 =c.sub.n-2 .alpha..sup.(b+n-k-1)(n-2) +c.sub.n-3 .alpha..sup.(b+n-k-1)(n-3) + . . . +c.sub.1 .alpha..sup.b+n-k-1).sub.+ c.sub.0 (4)
It is known that the thus formed extended RS code has a minimum distance of (n-k+1). Incidentally, the code before the extension (c.sub.n-2, C.sub.n-3, . . . , c.sub.1, c.sub.0) is called an interior code, and the symbol c.sub.-1, attached to the final place is called an extended component.
Here, the code word (c.sub.n-2, c.sub.n-3, . . . , c.sub.1, c.sub.0, c.sub.-1) of the singly extended RS code formed by adding to the final position the value c-.sub.1 generated by the foregoing expression (4) satisfies H.sup.t C=O, where H is a parity matrix given by the following expression (5), and .sup.t C represents the transpose of C. ##EQU1##
It is known that the thus formed extended RS code has a minimum distance d=n-k+1. Considering that the interior code has the minimum distance n-k, it is increased by one. When the minimum distance n-k equals 2t, where t is a positive integer, the interior code can correct only (t-1) errors. The singly extended RS code, however, can correct t errors because its minimum distance is 2t+1. In addition, when the interior code has the minimum distance n-k=2t+1, the minimum distance of the singly extended RS code is 2t+2, which can correct t errors and detect (t+1) errors (in which case, the total of t+l errors, t errors occurring in the interior code and one error in the extended component, can be corrected). Thus, the singly extended RS code improves correcting and detecting capability with one additional check symbol added to the normal RS code.
FIG. 30 is a flowchart illustrating the processing procedure of a conventional error correcting method of the singly extended RS code with a code length of n, information symbol number of k, and minimum distance of d=n-k+1=2t+1, where t is a positive integer. In FIG. 30, step ST60 is a syndrome generating step, ST61 is a Euclidean algorithm computing step, ST62 is a truth decision step, ST63 is a Euclidian algorithm computing step, ST64 is a truth decision step, ST65 is a Chien's search. step, and ST66 is an error correcting/detecting step.
Next, the operation will be described.
In the following description, it is assumed that R=(r.sub.n-2, r.sub.n-3, . . . , r.sub.0, r.sub.-1) is received as a received word R. First, in the syndrome generating step ST60, the syndrome S=(S.sub.0, S.sub.1, S.sub.2t-2, S.sub.2t-1) is computed by the following expression (6) EQU S=H.sup.t R (6)
where H is a parity matrix given by the foregoing expression (5).
Next, in the Euclidean algorithm computing step ST61, error-locator polynomials .sigma.(x) and error value polynomials .omega.(x) are computed by the Euclidean algorithm using polynomials given by the following expressions (7) and (8) as initial values. EQU i R.sub.-1 (x)=x.sup.2t-1 (7) EQU R.sub.0 (x)=S.sub.0 +S.sub.1 x+ . . . +S.sub.2t-2 x.sup.2t-2(8)
The ending condition of the Euclidean algorithm computing step ST61 is given by the following expression (9). EQU d e g R.sub.i (x)&lt;t-1 (9)
The computation of the error-locator polynomial and error-value polynomial in the Euclidean algorithm computing step ST61 is carried out in accordance with the procedure as shown in the flowchart of FIG. 31.
In the Euclidean algorithm computation, first, B.sub.-1 (x) and B.sub.0 (x) are set to zero and one, respectively, at step ST610, the initial values of R.sub.-1 (x) and R.sub.0 (x) are set as shown by the foregoing expressions (7) and (8), respectively, at step ST611, and the initial value of a variable i is set at one at step ST612. Next, quotient polynomial Q.sub.i (x) is obtained by dividing R.sub.i-2 (x) by R.sub.i.sub.1 (x) at step ST613, and R.sub.i (x) and B.sub.i (x) are computed by the following equations (10) and (11) using the quotient polynomial Q.sub.i (x) at step ST614. EQU R.sub.i (x)=Q.sub.i (x)R.sub.i-1 (x)+R.sub.i-2 (x) (10) EQU B.sub.i (x)=Q.sub.i (x) B.sub.i-1 (x)+B.sub.i-2 (x) (11)
Subsequently, a decision is made whether the degree of the R.sub.i (x) thus obtained satisfies the ending condition or not at step ST615. If the ending condition is not satisfied, the variable i is incremented at step ST616, and the processings from step ST613 onward are iterated. On the other hand, if the ending condition is satisfied, the error-locator polynomial .sigma.(x) and error-value polynomial .omega.(x) are computed by the following equations (12) and (13) at step ST617, thus completing the Euclidean algorithm computation. EQU .sigma.(x)=B.sub.i (x) (12) EQU .omega.(x)=R.sub.i (x) (13)
Subsequently, the candidates of the error-locator polynomial and error-value polynomial computed in Euclidean algorithm computing step ST61 are checked in the truth decision step ST62 whether they are true error-locator polynomial and error-value polynomial using the following expression (14). EQU d e g .omega.&lt;d e g .sigma..ltoreq.t-1 (14)
If the condition is satisfied, the Chien's search is performed in Chien's search step ST65 on the error-locator polynomial .sigma.(x) and error-value polynomial .omega.(x) computed in the Euclidean algorithm computing step ST61 to obtain the error locations and error values. Subsequently, in the error correcting/detecting step ST66, the error correcting operation is carried out if the errors are decided as correctable, thus completing the series of the processings.
On the other hand, if it is found in the truth decision step ST62 that the condition is not satisfied, the error-locator polynomial .sigma.(x) and error-value polynomial .omega.(x) are computed by the Euclidean algorithm by repeating the processings of FIG. 31 again using the polynomials given by the following equations (15) and (16) as the initial values. EQU R.sub.-1 (x)=x.sup.2t (15) EQU R.sub.0 (x)=S.sub.0 +S.sub.1 x+ . . . +S.sub.2t-2 x.sup.2t-2 +S.sub.2t-1 x.sup.2t-1 (16)
As the ending condition of the Euclidean algorithm computing step ST63, the following expression (17) is used. EQU d e g R.sub.i (x)&lt;t (17)
Subsequently, the candidates of the error-locator polynomial and error-value polynomial computed in the Euclidean algorithm computing step ST63 are checked in the truth decision step ST64 whether they are true error-locator polynomial and error-value polynomial using the following expression (18). EQU d e g .omega.&lt;d e g .sigma. (18)
If the condition is satisfied, the Chien's search is performed in Chien's search step ST65 on the error-locator polynomial .sigma.(x) and error-value polynomial .omega.(x) to obtain the error locations and error values. If the errors are correctable, the error correcting operation is carried out in the error correcting/detecting step ST66, thus completing the series of the processings. On the other hand, if it is found that the condition is unsatisfied as a result of the check in the truth decision step ST64, the processings in the error correcting/detecting step ST66 is stopped at the error detection, thus completing the series of the processings.
Next, a doubly extended RS code will be described. Here, for the purpose of simplicity, it is assumed that the characteristic of the Galois field is two.
A doubly extended RS code with a code length of n and an information symbol number of k can be formed as follows. First, an information polynomial with the following expression (19) is formed for information symbols (c.sub.n-3, c.sub.n-4, . . . , C.sub.n-k-2) consisting of the elements of the Galois field. EQU c.sub.n-3 x.sup.n-3 +c.sub.n-4 x.sup.n-4 + . . . +c.sub.n-k-2 x.sup.n-k-2 ( 19)
Then, the information polynomial is divided by a generator polynomial given by the following expression (20). EQU g(x)=(x-.alpha..sup.b)(x-.alpha..sup.b+1) . . . (x-.alpha..sup.n-k-2(20)
where b is a predetermined integer, and a is a root of a primitive polynomial forming the Galois field.
When the remainder polynomial obtained by the division by the foregoing expression (20) is given by the following expression (21), (c.sub.n-3, c.sub.n-4, . . . , c.sub.1, c.sub.0) is formed by adding coefficients of (n-k-2) symbols as check symbols. EQU c.sub.n-k-3 x.sup.n-k-3 +c.sub.n-k-4 x.sup.n-k-4 + . . . +c.sub.1 x+c.sub.0 (21)
Furthermore, a code word c=(c.sub.n-2, c.sub.n-3, . . . , c.sub.1, c.sub.0, c.sub.-1) of a doubly extended RS code is formed by adding c.sub.-1 and c.sub.n-2 generated by the following equations (22) and (23). EQU c.sub.-1 =c.sub.n-3 +c.sub.n-4 + . . . +c.sub.1 +c.sub.0 (22) EQU c.sub.n-2 =c.sub.n-3 .alpha..sup.(n-k-1)(n-3) +c.sub.n-4 .alpha..sup.(n-k-1)(n-4) + . . . +c.sub.1 .alpha..sup.n-k-1 +c.sub.0(23)
Here, the code word (c.sub.n-2, C.sub.n-3, . . . , c.sub.1, c.sub.0, c.sub.-1) of the doubly extended RS code formed by adding to the edge symbols the value c.sub.-1 and c.sub.n-2 generated by the foregoing expressions (22) and (23) satisfies H.sub.2.sup.t C=0, where H.sub.2 is a parity matrix given by the following expression (24), and .sup.t C represents the transpose of C. ##EQU2##
In this case also, the code before the extension (c.sub.n-3, c.sub.n-4, . . . , c.sub.1, c.sub.0) is called an interior code, and the symbol c.sub.-1 attached to the final position is called a first extended component, and the symbol c.sub.n-2 added to the initial position is called a second extended component.
It is known that the thus formed doubly extended RS code has a minimum distance of d=n-k+1. Considering that the interior code has the minimum distance of n-k-1, it is increased by two. Accordingly, one more error can be corrected in addition to the correcting capability of the interior code.
As a conventional error correcting method of the doubly extended RS code, the algorithm is known which is described, for example, in chapter 9, verse 3 of R. E. Blahut, "Theory and Practice of Error Control Codes", Addison-Wesley Publishing Company, 1984. FIG. 32 is a flowchart illustrating the processing procedure of the conventional error correcting method of the doubly extended RS code with a code length of n, information symbol number of k, and minimum distance of d=n-k+1=2t+1, where t is a positive integer.
In FIG. 32, step ST70 is a syndrome generating step, ST71 is a Berlekamp-Massey algorithm computing step, ST72 is a test step of an error-locator polynomial, ST73 is a Berlekamp-Massey algorithm computing step, ST74 is a test step of an error-locator polynomial, ST75 is a Berlekamp-Massey algorithm computing step, ST76 is a test step of an error-locator polynomial, ST77 is a Berlekamp-Massey algorithm computing step, ST78 is a test step of an error-locator polynomial, ST79 is a Chien's search step, ST80 is a test step of the number of roots, and step ST81 is an error correcting step.
Next, the operation will be described.
In the following description, it is assumed that a received word R=(r.sub.n-2, r.sub.n-3, . . . , r.sub.0, r.sub.-1) has been received. First, in the syndrome generating step ST70, the syndrome S=(S.sub.0, S.sub.1, S.sub.2t-2, S.sub.2t-1) is computed by the following expression (25). EQU S=H.sub.2.sup.t R (25)
where the error information on the first extended component is included in S.sub.0, and the error information on the second extended component is included in S.sub.2t-1.
Next, in the Berlekamp-Massey algorithm computing step ST71, the Berlekamp-Massey algorithm (BM1) is carried out using 2t-2 syndromes S.sub.1, . . . , S.sub.2t-2 including only error information occurred in the interior code. FIG. 33 is a flowchart illustrating the computation procedures of the Berlekamp-Massey algorithm for obtaining the error-locator polynomials.
The Berlekamp-Massey algorithm (BM1) will now be described with reference to FIG. 33.
First, the initial values are set at step ST710 as follows: the initial value of the error-locator polynomial, .sigma..sup.0 (x)=1; a formal shift register length L=0; a supplementary polynomial for updating the error-locator polynomial, .tau..sup.0 (x)=1; and a variable for counting the number of steps, r=1.
Let us assume that the error-locator polynomials are sequentially computed, and after having completed an (r-1)-th step, the error-locator polynomial .sigma..sup.(r-1) (x) and supplementary polynomial .tau..sup.(r-1) (x) are computed. At the r-th step, a discrepancy .DELTA..sub.r given by the following expression (26) is computed using the coefficients of .sigma..sup.(r-1) (x) at step ST711. ##EQU3##
Next, the computation result is checked at step ST712, and if the discrepancy .DELTA..sub.r is zero, the error-locator polynomial is not updated, but .sigma..sup.(r-1) (x) obtained at the (r-1)-th computation is adopted as the r-th error-locator polynomial at step ST713. On the other hand, if the discrepancy .DELTA..sub.r is nonzero, connection polynomial .eta.(x) is formed by the following expression (27) using the supplementary polynomial .tau..sup.(r-1) (x) at step ST714. EQU .eta.(x).rarw..sigma..sup.(r-1) (x)+.DELTA..sub.r x.tau..sup.(r-1) (x)(27)
Next, a decision is made whether formal shift register length L satisfies 2L&lt;r at step ST715, and if it satisfies, the supplementary polynomial .tau..sup.(r) (x), the error-locator polynomial .sigma..sup.(r) (x), and the formal shift register length L are updated as the following expressions (28)-(30) at step ST716. EQU .tau..sup.(r) (x).rarw..DELTA..sub.r.sup.-1 .tau..sup.(r-1) (x) (28) EQU .sigma..sup.(r) (x).rarw..eta.(x) (29) EQU L.rarw.r-L (30)
On the other hand, if the inequality is unsatisfied, the formal shift register length L is not updated, but the error-locator polynomial .sigma..sup.(r) (x) is updated as the following expression (31) at step ST717, and the supplementary polynomial .tau..sup.(r) (x) is updated as the following expression (32) at step ST713. EQU .sigma..sup.(r) (x).rarw..eta.(x) (31) EQU .tau..sup.(r) (x).rarw.x.tau..sup.(r-1) (x) (32)
Then, the processings from step ST711 onward are iterated with incrementing the variable r for counting the step number at step ST719 until it is found that the variable r reaches 2t-2 at step ST718.
When the Berlekamp-Massey algorithm (BM1) in the Berlekamp-Massey algorithm computing step ST71 has completed, the error-locator polynomial .sigma.(x) is tested whether it is appropriate or not in the test step ST72. .Here, if at most t=2 errors have occurred in the interior code, the (2t-3)-th and (2t-2)-th discrepancy are zero, and after the Berlekamp-Massey algorithm (BM1) has been completed, the formal shift register length L is equal to or less than t-2, and the degree of the error-locator polynomial .sigma..sup.(2t-2) (x) equals the formal shift register length L. Thus, if the error-locator polynomial .sigma..sup.(2t-2) (x) satisfies the following conditions (33), the processing makes a decision that the error-locator-polynomial .sigma..sup.(2t-2) (x) is appropriate and proceeds to Chien's search step ST79 to perform the Chien's search after substituting .sigma.(x)=.sigma..sup.2t-2) (x) . EQU .DELTA..sub.2t-3 =0, .DELTA..sub.2t-2 =0, .DELTA.L.ltoreq.t-2, d e g .sigma..sup.(2t-2) =L (33)
On the other hand, if the foregoing conditions (33) do not hold, it is assumed that at least t-1 errors have occurred in the interior code and one more step of Berlekamp-Massey algorithm (BM1') is carried out using S.sub.2t-1 in Berlekamp-Massey algorithm computing step ST73. Then, in test step ST74, error-locator polynomial .sigma.(x) is tested whether it is appropriate or not. If t-1 errors have occurred in the interior code with no error occurring in the second extended component, the discrepancy .DELTA..sub.2t-1 becomes zero. In addition, the degree of the error-locator polynomial .sigma..sup.(2t-1) (x)(=.sigma..sup.(2t-2) (x)) equals the formal shift register length L. Thus, if the error-locator polynomial .sigma. .sup.(2t-1) (x) satisfies the following conditions (34), the processing makes a decision that the error-locator polynomial .sigma..sup.(2t-1) (x) is appropriate and proceeds to Chien's search step ST79 to perform the Chien's search after substituting .sigma.(x)=.sigma..sup.2t-1) (x). EQU .DELTA..sub.2t-1 =0, d e g .sigma..sup.(2t-1) =L (34)
On the other hand, if the conditions given by the foregoing expression (34) do not hold, it is assumed that at least t errors have occurred in the interior code and Berlekamp-Massey algorithm (BM2) is performed again using syndromes S.sub.0, S.sub.1, . . . , S.sub.2t-2, and S.sub.2t-1 in the Berlekamp-Massey algorithm computing step ST75. The Berlekamp-Massey algorithm (BM2) is basically the same as the Berlekamp-Massey algorithm (BM1), but the computation of the discrepancy is carried out using the following equation (35). ##EQU4##
Then, in the test step ST74, error-locator polynomial .sigma.(x) is tested whether it is appropriate or not. If t-1 errors have occurred in the interior code with no error occurring in the first extended component, the discrepancy .DELTA..sub.2t-1 becomes zero. In addition, the degree of the error-locator polynomial .sigma..sup.(2t-1) (x) (=.sigma..sup.2t-2) (x)) equals the formal shift register length L after the completion of the Berlekamp-Massey algorithm (BM2). Thus, if the error-locator polynomial .sigma..sup.(2t-1) (x) satisfies the conditions of expression (34), the processing makes a decision that the error-locator polynomial .sigma.(.sup.2t-1) (x) is appropriate and proceeds to the Chien's search step ST79 to perform the Chien's search after substituting .sigma.(x)=.sigma..sup.(2t-2)(x).
On the other hand, if the conditions of expression (34) do not hold, it is assumed that at least t errors have occurred in the interior code, and one more step of Berlekamp-Massey algorithm (BM2') is carried out using S.sub.2t-1 in Berlekamp-Massey algorithm computing step. ST77. If no errors have occurred in both the extended components, the degree of the error-locator polynomial .sigma..sup.(2t) (x) and the formal shift register length L are equal to t after the completion of the Berlekamp-Massey algorithm (BM2'). Thus, if the conditions of the following expression (36) hold, the processing makes a decision that the error-locator polynomial .sigma..sup.(2t) (x) is appropriate and proceeds to the Chien's search step ST79 to perform the Chien's search after substituting .sigma.(x)=.sigma..sup.(2t) (x). EQU d e g .sigma..sup.(2t) =L=t (36)
On the other hand, if the conditions of expression (36) do not hold, it is assumed that at least t+1 errors have occurred, and the received word R is output without correction along with the error detection flags, indicative of uncorrectable errors.
If the error-locator polynomial can be detected in any of the Berlekamp-Massey algorithm computing steps ST71, ST73, ST75 and ST77, the Chien's search is carried out in the Chien's search step ST79 to computed the roots (error locations) of the error-locator polynomial .sigma.(x). Subsequently, in the test step ST80, a decision is made whether the number of the obtained roots of the error-locator polynomial .sigma.(x) equals the degree of the error-locator polynomial .sigma.(x), and if they agree with each other, the error values are computed in the error-correcting step ST81, and the errors are corrected by subtracting the error values from the symbols at the error locations of the received word R.
If the number of the obtained roots of the error-locator polynomial .sigma.(x) does not agree with the degree of the error-locator polynomial .sigma.(x), the received word R is output without correction along with the error detection flag, indicating that the errors are uncorrectable.
The conventional error correction of the singly extended RS code thus performed is complicated in algorithm, in which the Euclidean algorithm computation must be performed twice in the worst case. This presents a problem of prolonging the time needed for decoding. Furthermore, there are no known documents about the erasure and error correction of the singly extended RS code, which presents a problem in that it is necessary to develop an effective erasure and error correcting method and apparatus.
Besides, since the conventional error correction of the doubly extended RS code is thus performed, it is complicated in algorithm and requires two steps of the Berlekamp-Massey algorithm computations in the worst case. This presents a problem of prolonging the time needed for decoding. Furthermore, there are no known documents about the erasure and error correction of the doubly extended RS code, which presents a problem in that it is necessary to develop an effective erasure and error correcting method and apparatus.